package com.jwetherell.my.problems.dynamicprogramming;

public class FibonacciSum {

	public static void main(String[] args) {
		FibonacciSum fibonacciSum = new FibonacciSum();
		int input = 44;

		System.out.println(String.format("Sum of %d is\n", input));

		String TIME_STR_PREFIX = " [Time: ";
		String TIME_STR_SUFFIX = " milliseconds]";
		int divisor = 1;
		long startTime;
		long totalTime;
		
		// Recursive
		startTime = System.currentTimeMillis();
		int sum = fibonacciSum.computeSumRecursively(input);
		totalTime = (System.currentTimeMillis() - startTime) / divisor;
		System.out.println("Recursive: " + sum + TIME_STR_PREFIX + totalTime + TIME_STR_SUFFIX);

		// DP - Memoization (Top Down) - Similar to recursive solution
		startTime = System.currentTimeMillis();
		fibonacciSum.dpLookupArray = new int[input + 1];
		fibonacciSum.initDPLookupArray(input);
		sum = fibonacciSum.computeSumThroughDP_Memoization(input);
		totalTime = (System.currentTimeMillis() - startTime) / divisor;
		System.out.println("DP Memoization: " + sum + TIME_STR_PREFIX + totalTime + TIME_STR_SUFFIX);

		// DP - Tabulation (Bottom Up)
		startTime = System.currentTimeMillis();
		sum = fibonacciSum.computeSumThroughDP_Tabulation(input);
		totalTime = (System.currentTimeMillis() - startTime) / divisor;
		System.out.println("DP Tablution: " + sum + TIME_STR_PREFIX + totalTime + TIME_STR_SUFFIX);
	}

	
	
	/*
	 * DP - Dynamic Programming -> Tabulation (Bottom Up)
	 * 
	 * The tabulated program for a given problem builds a table in bottom up fashion and returns the last entry from table.
	 * 
	 * Note: Unlike DP-Memoization(Top Down), this is not recursive
	 */
	private int computeSumThroughDP_Tabulation(int n) {
		
		int [] table = new int [n+1]; // DP lookup table
		
		table[0] = 0; // base-case in corresponding recursive solution
		table[1] = 1; // base-case in corresponding recursive solution
		
		for (int i = 2; i <= n; i++) // start loop after the base-cases to calculate results for rest of the cases till case 'n'
			table[i] = table [i-1] + table[i-2]; // calculating the current result with the help of previous results
		
		return table[n]; // returns the desired result from the calculated results
	}


	
	/*
	 * DP - Dynamic Programming -> Memoization (Top Down) 
	 * 
	 * The memoized program for a problem is similar to the recursive version with a small
	 * modification that it looks into a lookup table before computing
	 * solutions. We initialize a lookup array with all initial values as NIL.
	 * Whenever we need solution to a subproblem, we first look into the lookup
	 * table. If the precomputed value is there then we return that value,
	 * otherwise we calculate the value and put the result in lookup table so
	 * that it can be reused later.
	 */
	private static final int DP_LOOK_UP_ARRAY_NIL_VALUE = -1;
	private int[] dpLookupArray;

	private void initDPLookupArray(int n) {
		for (int i = 0; i < n+1; i++)
			dpLookupArray[i] = DP_LOOK_UP_ARRAY_NIL_VALUE; 
	}
	
	private int computeSumThroughDP_Memoization(int n) {
		if (dpLookupArray[n] == DP_LOOK_UP_ARRAY_NIL_VALUE) {
			// Logic in this if block is same as the recursive solution
			if (n <= 1)
				dpLookupArray[n] = n; // b'coz fib(0)=0 and fib(1)=1
			else
				dpLookupArray[n] = computeSumThroughDP_Memoization(n-1) + computeSumRecursively(n-2);
		}
		return dpLookupArray[n];
	}

	
	
	
	
	/*
	 * Recursive solution
	 */
	private int computeSumRecursively(int n) {
		if (n <= 1)
			return n;
		return computeSumRecursively(n - 1) + computeSumRecursively(n - 2);
	}

}
